算法与数据结构学习笔记

一串字符中可能进行多次查找，每个字符被查找到的频率都不同，如何根据字符被查找到的频率，建立一个二叉搜索树，使得花费时间最少呢？

题目：给定一列按升序排列的键值 K = [ k 1 , k 2 , . . . , k n ] K=[k_1,k_2,...,k_n] K=[k1​,k2​,...,kn​]和它们被搜索到的频率 P = [ p 1 , p 2 , . . . , p n ] P=[p_1,p_2,...,p_n] P=[p1​,p2​,...,pn​]，建立一个二叉搜索树，使得搜索的平均费用最低。要求输入键值和频率数组，返回搜索树及其费用。

二叉树的费用如何计算呢？我们知道节点越低，搜索经过的路程越长。因此定义搜索的花费 c o s t ( k i ) = d e p t h ( k i ) + 1 cost(k_i)=depth(k_i)+1 cost(ki​)=depth(ki​)+1。因为对根节点进行查找也需要一次操作，而根节点的深度为0,所以定义每个节点的搜索花费为 d e p t h ( k i ) + 1 depth(k_i)+1 depth(ki​)+1。每一个节点 k i k_i ki​被搜索到的频率为 p i p_i pi​，因此整棵树T的费用定义为：

E ( T ) = ∑ i = 1 n c o s t ( k i ) ⋅ p i = ∑ i = 1 n ( d e p t h ( k i ) + 1 ) ⋅ p i = ∑ i = 1 n d e p t h ( k i ) ⋅ p i + ∑ i = 1 n p i E(T)=\sum_{i=1}^{n} cost(k_i) \cdot p_i= \sum_{i=1}^{n} (depth(k_i)+1)\cdot p_i= \sum_{i=1}^{n} depth(k_i) \cdot p_i+\sum_{i=1}^{n} p_i E(T)=i=1∑n​cost(ki​)⋅pi​=i=1∑n​(depth(ki​)+1)⋅pi​=i=1∑n​depth(ki​)⋅pi​+i=1∑n​pi​ 而 ∑ i = 1 n p i \sum_{i=1}^{n} p_i ∑i=1n​pi​的值为1（每个键值的概率相加），因此 E ( T ) = ∑ i = 1 n d e p t h ( k i ) ⋅ p i + 1 E(T)=\sum_{i=1}^{n} depth(k_i) \cdot p_i+1 E(T)=i=1∑n​depth(ki​)⋅pi​+1

在搜索过程中会出现对给出的键值之外的值的搜索，为了方便，我们给搜索树的每个叶子节点加上两个“假的”节点，并给出搜索到假节点的概率用 q 0 , q 1 , . . . , q n q_0, q_1, ...,q_n q0​,q1​,...,qn​表示。

用该公式尝试计算一棵二叉搜索树的费用：

左树 E ( T ) = ∑ i = 1 n d e p t h ( k i ) ⋅ p i + 1 = 0.20 × 0 + 0.25 × 1 + 0.20 × 1 + 0.05 × 2 + 0.30 × 2 + 1 = 2.15 E(T)=\sum_{i=1}^{n} depth(k_i)\cdot p_i+1=0.20×0+0.25×1+0.20×1+0.05×2+0.30×2+1=2.15 E(T)=i=1∑n​depth(ki​)⋅pi​+1=0.20×0+0.25×1+0.20×1+0.05×2+0.30×2+1=2.15 右树 E ( T ) = ∑ i = 1 n